#ifndef STAINING_METHOD_H
#define STAINING_METHOD_H
#include<QVector>

class Staining_method
{
public:
    Staining_method();
    bool dfs(int u, const QVector<QVector<int>>& g, QVector<int>& col)
    {
        for (int v : g[u])
        {
            if (col[v] == -1)//假设所有颜色未被染色
            {
                col[v] = 1 - col[u];//结果只有0和1，便于分开不同颜色的集合
                if (!dfs(v, g, col))
                    return false;
            }
            else if (col[u] == col[v]) return false;//分支，都染色的情况
        }
        return true;
    }

    bool possibleBipartition(int n, QVector<QVector<int>>& dislikes)
    {
        QVector<QVector<int>> g(n);
        for (auto& v : dislikes)
        {
            int x = v[0] - 1, y = v[1] - 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        QVector<int> col(n, -1);

        for (int i = 0; i < n; i++)//循环从0开始，避免了不连通的情况
            if (col[i] == -1)
            {
                col[i] = 0;
                if (!dfs(i, g, col))
                    return false;//出现奇数环的情况，报错
            }
        return true;
    }
};

#endif // STAINING_METHOD_H
